Defining a method for managing anonymous certificates for vehicle communications networks, such as the Vehicle Infrastructure Integration (VII) system, is a very difficult, complex, and multi-faceted technical challenge. A significant part of this challenge is to protect vehicle privacy, i.e., secure vehicle communications so that the source remains anonymous and messages cannot be linked to one another. At the same time, misbehaving vehicles and attackers need to be detected and removed from the system. Traditional certificate management techniques are unacceptable because they use certificates that can readily identify the user and do not preserve vehicle privacy. No anonymous certificate method proposed to date has completely satisfied all design goals. Each offers a different balance of competing and intricately interrelated objectives, which include vehicle privacy, system security, system scalability, system robustness, vehicle segment maintenance, low complexity, practical implementation and ubiquitous operation.
Various categories of approaches for the management of anonymous keys and certificates are known. One popular category includes combinatorial certificate schemes that are shared-key approaches where each vehicle uses a small number of keys and certificates that are drawn randomly from a shared pool of keys and certificates. The keys in the pool can be created by a key-generation algorithm. Privacy is achieved because each key and certificate is shared by many vehicles. However, the balance among scalability, privacy, and performance in this category is limited.
The main operations in the anonymous certificate management process are 1) testing, 2) initialization, 3) selection and rotation, and 4) revocation and replacement of anonymous keys and certificates. Testing of anonymous keys and certificates can be performed by both vehicle suppliers and vehicle original equipment manufacturers (OEMs) to ensure the correct functioning of the key and certificate generation software and hardware components.
Initialization of anonymous keys and certificates involves the interaction between vehicles, vehicle dealers, and vehicle OEMs to allow vehicles to obtain their initial sets of live anonymous keys and certificates. Once a vehicle is initialized with its long-lasting keys and certificates, such as the 1609.2 CSR certificates, the vehicle can use these long-lasting keys and certificates to acquire initial anonymous keys and certificates in the same manner as it will acquire subsequent anonymous keys and certificates.
Selection and rotation of anonymous keys and certificates includes procedures used by each vehicle to select the anonymous keys and certificates to use and to decide how and when to rotate (change) the anonymous certificates each vehicle uses.
Revocation and replacement of anonymous keys and certificates determines which anonymous certificates should be revoked, revoking these certificates from the vehicles and the VII or other vehicle network system, and providing new keys and certificates to replace the revoked keys and certificates on the vehicles. However, certificate revocation and replacement methods in the basic combinatorial certificate schemes have several crucial limitations that need to be overcome. First, they cannot support a moderate to high number of attackers. Second, they will result in unpredictable and uncontrollable probability distributions of certificates among vehicles, resulting in unpredictable and uncontrollable system scalability and performance. Third, they are missing some necessary methods to ensure the continuous operation of the certificate management system. For example, they use a fixed rekey threshold to determine which vehicles should no longer be allowed to receive new anonymous certificates, but do not provide a method for decrementing or resetting the rekey counters.
Combinatorial certificate management schemes exhibit a fundamental weakness, known as the “one affects many” problem. The “one affects many” problem refers an inherent attribute of shared certificate schemes where a threat to a certificate held by one vehicle is amplified by the sharing of keys and affects a large number of vehicles. In particular, the “one affects many” problem manifests itself in the following ways:
1. A large number of innocent vehicles are impacted when a certificate is revoked
2. Mean time to vehicle inspection (i.e., locked-out vehicles) is short
3. Vulnerable to “Large Scale” Attacks
4. Difficult to identify the source of malicious messages
The sharing of a common pool of keys forms the basis of vehicle anonymity in the combinatorial scheme, but it is also the root of the “one affects many” problem. Using a random key distribution, the number of vehicles sharing a certificate in a system with v vehicles, where each holds n certificates from a pool of N, is approximately vn/N. If n=5, N=10,000, and v=200,000,000, the number of vehicles sharing the same certificate is 100,000. Hence, if just one certificate is revoked because of a single misbehaving vehicle, about 100,000 vehicles are impacted. In essence, a large number of innocent vehicles potentially become “collateral damage” from the revocation of a single certificate. The amount of “collateral damage” grows with the number of certificates that are revoked. Geographic zoning is being considered as a potential way to reduce “collateral damage.”
If an innocent vehicle becomes the unfortunate victim of a large number of certificate revocations, the vehicle may trigger the enforcement of a re-keying quota. Once a vehicle has reached its re-keying quota, the vehicle is locked-out, i.e., not allowed to re-key, and must be physically inspected before it can rejoin the system as an active participant. Although the intent of the quota is to limit re-keying for misbehaving vehicles, some innocent vehicles will unnecessarily trigger disciplinary actions as “false positives.” When the effect is measured as the mean time to vehicle inspection, the combinatorial scheme has been shown to be very sensitive to the number of misbehaving vehicles. For instance, with just a few thousand misbehaving vehicles each year, the mean time to vehicle inspection can be 24 to 36 months, i.e., each vehicle will need to be inspected every two to three years on average. In a system with 200,000,000 vehicles, this results in an undesirable inspection rate of five to eight million vehicles per month.
Any attack that can exploit the “one affects many” weakness in the combinatorial scheme is a serious concern. One particularly damaging attack that efficiently exploits this weakness is the “Large Scale” attack. In a “Large Scale” attack, a large number of certificates are compromised by, for instance, extracting the key information from vehicles. Since the shared pool of certificates is relatively small with respect to the number of vehicles in the system, an attacker need only compromise a relatively small number of vehicles to impact a very large percentage of all vehicles. With N=10,000, a compromise of just 500 vehicles will yield, with 90% probability, more than 20% of the shared pool of certificates. Such an attack would affect about two thirds of the vehicle population, or about 135 million vehicles.
The sharing of certificates, while providing the benefit of anonymity, also makes it difficult to identify misbehaving vehicles. A certificate associated with a malicious message cannot be immediately traced to any particular vehicle. Using the earlier example, the misbehaving vehicle can be any one of 100,000 vehicles.
The detection and removal of a misbehaving vehicle in a vehicle network system is a three step process. First, vehicle messages must be inspected and a determination must be made about whether they are malicious in nature. Second, each malicious message must be traced to a vehicle source. Third, the vehicle source must be disabled from generating messages that will be interpreted as legitimate in the vehicle network system.
Due to the nature of vehicle communication, its non-transactional behavior, and the size of a nationwide vehicle network system, the first step of detecting malicious messages and particularly, those with valid signatures, is an extremely difficult and challenging task. Depending upon the message context, it may be very difficult to delineate malicious message from a valid message. Legitimate messages may on occasion be incorrectly classified as malicious. Some types of malicious behavior may also be beyond the system's ability to detect it. There is also a certain amount of delay in detecting malicious behavior. Some malicious messages may not be observed because it may be impractical to inspect all vehicle messages. The use of thresholds to tally malicious events before taking an action inherently introduces delay. It is also likely that the threshold level will vary depending upon the type of malicious behavior. Some forms may require only one occurrence to trigger action. Others may require multiple occurrences.
In shared certificate schemes, such as the combinatorial scheme, the second step of identifying the vehicle source of a malicious message, which relies upon the consistency and accuracy of the first, is also a difficult and complicated task. Many methods employ techniques that narrow the set of potential vehicles with each re-keying using a multi-round abatement process. But this process could require many rounds to identify the misbehaving vehicle. For instance, if 100,000 vehicles share a single common certificate, it could take up to log2 (100,000) or 16 rounds of re-keying to identify the individual vehicle source, assuming the vehicle population is narrowed by a factor of two on each round. There are several concerns with multi-step approaches:                Unreliable detection of malicious behavior will delay or potentially undermine the process to identify a misbehaving vehicle.        Each of the multiple rounds of re-keying needed to identify a misbehaving vehicle provides an opportunity for the attacker to change its mode of attack and potentially evade discovery.        Each round of re-keying introduces additional delay and extends the period of time that an attacker can continue operating.        Multiple, simultaneous attacks make identification of misbehaving vehicles more difficult and increase the probability that an innocent vehicle will be identified as a misbehaving vehicle.        
The third step of disabling a misbehaving vehicle from generating messages that will be interpreted as legitimate is accomplished by revoking certificates using a certificate revocation list (CRL) and locking out vehicles with either a static or dynamic re-keying quota. Neither effort is instantaneous. CRLs need to be distributed over the air-link to vehicles. The distribution process may require a period of time before every vehicle has received the updated CRL. During this period of time, misbehaving vehicles can still operate. More importantly, once a certificate has been revoked, a misbehaving vehicle can request a replacement certificate and continue to operate. The number of times the misbehaving vehicle can replace its revoked certificates varies depending upon the algorithm used to identify misbehaving vehicles, but it is typically in the range of eight to twenty-five times, depending upon the efficiency of the algorithm.
Finally, another undesirable aspect of the combinatorial scheme is the high probability that all vehicles in a given area will share no common certificates. Despite the sharing of certificates at a system wide level, there is a fairly significant probability that all certificates are unique. When combined with the use of a small number of certificates per vehicle, it is not too difficult to begin linking messages to a particular vehicle source and tracking a vehicle, thereby violating its privacy and anonymity.
The prior art combinatorial scheme has several drawbacks and limitations with preserving privacy, exhibiting strong sensitivity to the number of attackers, and being able to quickly and accurately remove misbehaving vehicles, which are inherent from the sharing of certificates. There is a need for a carefully designed anonymous certificate revocation and replacement process to ensure that the anonymous certificate management system can achieve proper balances among critical objectives, such as scalability, privacy, and performance, and can simplify the identification and removal of misbehaving vehicles.
The following defined terms are used throughout, and VII can be replaced with another vehicle network system.
Anonymous Certificate: A certificate associated with a public-private key pair that, when used by vehicles, will not enable the identification and tracking of vehicles. In a combinatorial certificate scheme, each anonymous certificate will be shared among many vehicles in the VII system. The certificate is attached to a signed message that is generated by a vehicle and is used to verify the digital signature.
Anonymous Key: A private-public key pair that is shared among many vehicles in the VII system and is used to sign messages. Anonymous private keys are highly confidential and any compromise of an anonymous key can threaten the integrity of the VII system.
Attacker: Any entity that may be using anonymous keys and certificates to harm, damage, or manipulate the VII system either maliciously or unintentionally.
Attacker Elimination: The process of removal or rendering an attacker harmless to the VII system. Examples of attacker elimination include proactive system measures, such as locking out a vehicle (i.e., completely revoking all anonymous certificates on a vehicle), and pushing an attacker out of the system by means of certificate expiration.
Certificate: An electronic form of credential that uses a digital signature of a trustworthy authority to attest to the binding of a public key with an identity and/or a set of permissions.
Lock-out: An action taken by the VII system to deny certificate requests, typically because of excessive rekey attempts.
Private Application: An optional value-add service selected by the vehicle owner or occupant that is delivered using the VII system.
Private Key: An encryption/decryption code mathematically related to a paired public key in an asymmetric cryptographic system. A private key is held in secret and is used to decrypt information encrypted by its paired public key or sign information as proof of authenticity or integrity.
Public Application: A mandatory service in the VII system, generally for public safety or improved mobility, that all vehicles participate in using anonymous messages.
Public Key: An encryption code mathematically related to a paired private key in an asymmetric cryptographic system. A public key is shared and used to encrypt information that can only be decrypted by its paired private key. It is computationally infeasible to derive a private key from a public key.
Vehicle Segment: The collection of hardware and software installed in each vehicle that supports VII functions.